public class TraversalBT {
    private static class Node{
        int value;
        Node left;
        Node right;
        Node(int v){
            value = v;
        }
    }

    public static void pre(Node head){
        if (head == null){
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()){
            head = stack.pop();
            System.out.print(head.value + " ");

            if (head.right != null){
                stack.add(head.right);
            }
            if (head.left != null){
                stack.add(head.left);
            }
        }
    }

    public static void last(Node head){
        if (head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        Stack<Node> tmp = new Stack<>();
        while (!stack.isEmpty()){
            head = stack.pop();
            tmp.add(head);
            if (head.left != null){
                stack.add(head.left);
            }
            if (head.right != null){
                stack.add(head.right);
            }
        }

        while (!tmp.isEmpty()){
            head = tmp.pop();
            System.out.print(head.value + " ");
        }
    }

    public static void in(Node head){
        if (head == null){
            return;
        }

        Stack<Node> stack = new Stack<>();

        while(!stack.isEmpty() || head != null){
            if (head != null){
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

//        pre(head);
//        last(head);

        in(head);
    }
}
